#pragma once
#pragma warning(disable: 4290)

#include "utility.h"
#include "iterator.h"
#include <initializer_list>
#include <exception>

namespace qyc
{
	template<class T, size_t BufSiz> class deque;

	template<class T, size_t N>
	struct __deque_const_iterator
	{
		typedef T data_type;
		typedef const data_type& reference_type;
		typedef const data_type* pointer_type;
	private:
		typedef data_type** map_pointer;
		typedef __deque_const_iterator<data_type, N> self;

		friend class deque<data_type, N>;

		data_type* _cur = nullptr;
		map_pointer _node = nullptr;
		data_type* _first = nullptr;
		data_type* _last = nullptr;
	public:
		__deque_const_iterator() = default;
		explicit __deque_const_iterator(data_type* cur, map_pointer node)
			: _cur(cur)
			, _node(node)
			, _first(*_node)
			, _last(_first + N)
		{}

		reference_type operator*() const {
			return *_cur;
		}
		pointer_type operator->() const {
			return &(*_cur);
		}
		reference_type operator[](long long n) const {
			return *((*this) + n);
		}
		
		bool operator>(const self& it) const {
			return (_node == it._node) ? (_cur > it._cur) : (_node > it._node);
		}
		bool operator>=(const self& it) const {
			return !(*this < it);
		}
		bool operator<(const self& it) const {
			return (_node == it._node) ? (_cur < it._cur) : (_node < it._node);
		}
		bool operator<=(const self& it) const {
			return !(*this > it);
		}
		bool operator==(const self& it) const {
			return _cur == it._cur;
		}
		bool operator!=(const self& it) const {
			return _cur != it._cur;
		}

		self& operator++()
		{
			++_cur;
			if (_cur == _last)
			{
				set_node(_node + 1);
				_cur = _first;
			}
			return *this;
		}
		self operator++(int) {
			self ret = *this;
			++(*this);
			return ret;
		}
		self& operator--()
		{
			if (_cur == _first)
			{
				set_node(_node - 1);
				_cur = _last;
			}
			--_cur;
			return *this;
		}
		self operator--(int) {
			self ret = *this;
			--(*this);
			return ret;
		}
		self& operator+=(long long n)
		{
			if (n < 0)
				return (*this) -= (-n);
			long long offset = (_cur - _first) + n;
			long long node_offset = offset / N;
			long long cur_offset = offset % N;
			set_node(_node + node_offset);
			_cur = _first + cur_offset;
			return *this;
		}
		self operator+(long long n) const {
			self ret = *this;
			return ret += n;
		}
		self& operator-=(long long n)
		{
			if (n < 0)
				return (*this) += (-n);
			long long offset = ((_last - 1) - _cur) + n;
			long long node_offset = offset / N;
			long long cur_offset = offset % N;
			set_node(_node - node_offset);
			_cur = (_last - 1) - cur_offset;
			return *this;
		}
		self operator-(long long n) const {
			self ret = *this;
			return ret -= n;
		}
		long long operator-(const self& right) const {
			long long buf_distance = (_node - right._node) * N;
			long long pos_distance = (_cur - _first) - (right._cur - right._first);
			return buf_distance + pos_distance;
		}
		
		void swap(self& right)
		{
			qyc::swap(_cur, right._cur);
			qyc::swap(_first, right._first);
			qyc::swap(_last, right._last);
			qyc::swap(_node, right._node);
		}
	protected:
		void set_node(map_pointer node) {
			_node = node;
			_first = *_node;
			_last = _first + N;
		}
	};

	template<class T, size_t N>
	struct __deque_iterator : public __deque_const_iterator<T, N>
	{
		typedef T data_type;
		typedef data_type& reference_type;
		typedef data_type* pointer_type;
	private:
		typedef data_type** map_pointer;
		typedef __deque_iterator<data_type, N> self;
		typedef __deque_const_iterator<data_type, N> base_class;

		friend class deque<data_type, N>;
	public:
		__deque_iterator() = default;
		explicit __deque_iterator(data_type* cur, map_pointer node)
			: base_class(cur, node)
		{}

		reference_type operator*() const {
			return const_cast<reference_type>(base_class::operator*());
		}
		pointer_type operator->() const {
			return &(operator*());
		}
		reference_type operator[](long long n) const {
			return const_cast<reference_type>(base_class::operator[](n));
		}

		self& operator++() {
			base_class::operator++();
			return *this;
		}
		self operator++(int) {
			self ret = *this;
			base_class::operator++();
			return ret;
		}
		self& operator--() {
			base_class::operator--();
			return *this;
		}
		self operator--(int) {
			self ret = *this;
			base_class::operator--();
			return ret;
		}
		self& operator+=(long long n) {
			base_class::operator+=(n);
			return *this;
		}
		self operator+(long long n) const {
			self ret = *this;
			return ret += n;
		}
		self& operator-=(long long n) {
			base_class::operator-=(n);
			return *this;
		}
		self operator-(long long n) const {
			self ret = *this;
			return ret -= n;
		}
		long long operator-(const self& right) const {
			return base_class::operator-(right);
		}
	};

	template<class T, size_t BufSiz = 10>
	class deque
	{
		typedef T data_type;
		typedef data_type& reference;
		typedef const data_type& const_reference;
		typedef data_type* pointer;
		typedef const data_type* const_pointer;

		typedef T** map_pointer;
		typedef deque<data_type, BufSiz> self;
	public:
		typedef __deque_iterator<data_type, BufSiz> iterator;
		typedef __deque_const_iterator<data_type, BufSiz> const_iterator;
		typedef __reverse_iterator<iterator> reverse_iterator;
		typedef __reverse_iterator<const_iterator> const_reverse_iterator;

		deque()
		{
			new(this)self(0, data_type());
		}
		deque(const deque& right)
			: _map_size(right._map_size)
			, _map(new data_type* [_map_size]{nullptr})
		{
			map_pointer begin = _map + (right._start._node - right._map);
			*begin = static_cast<data_type*>(operator new(sizeof(data_type) * BufSiz));
			_finish = _start = iterator(*begin + (right._start._cur - right._start._first), begin);

			for (iterator first = right._start; first < right._finish; ++first)
				push_back(*first);
			//map_pointer end = _map + (right._finish._node - right._map);
			//for (size_t i = 0; begin + i <= end; ++i)
			//{
			//	begin[i] = static_cast<T*>(operator new(sizeof(data_type) * BufSiz));
			//	for (size_t j = 0; j < BufSiz; ++j)
			//		new(begin[i] + j)data_type(right._start._node[i][j]);
			//}
		}
		deque(deque&& right) noexcept
		{
			swap(right);
		}
		self& operator=(const deque& right)
		{
			if (&right != this)
			{
				self tmp(right);
				swap(tmp);
			}
			return *this;
		}
		self& operator=(deque&& right)
		{
			swap(right);
			return *this;
		}
		deque(size_t n, const data_type& data)
			: _map_size(n / BufSiz + 2)
			, _map(new data_type* [_map_size] {nullptr})
		{
			map_pointer begin = _map + _map_size / 2;
			*begin = static_cast<data_type*>(operator new(sizeof(data_type) * BufSiz));
			_finish = _start = iterator(*(_map + _map_size / 2), _map + _map_size / 2);
			for (size_t i = 0; i < n; ++i)
				push_back(data);
		}
		deque(int n, const data_type& data)
		{
			new(this)self(static_cast<size_t>(n), data);
		}
		deque(long n, const data_type& data)
		{
			new(this)self(static_cast<size_t>(n), data);
		}
		explicit deque(size_t n)
		{
			new(this)self(n, data_type());
		}
		template<class InputIterator>
		deque(InputIterator first, InputIterator last)
		{
			insert(begin(), first, last);
		}
		deque(std::initializer_list<data_type> _Ilist)
		{
			insert(begin(), _Ilist.begin(), _Ilist.end());
		}


		iterator begin()
		{
			return _start;
		}
		iterator end()
		{
			return _finish;
		}
		const_iterator begin() const
		{
			return _start;
		}
		const_iterator end() const
		{
			return _finish;
		}
		reverse_iterator rbegin()
		{
			return _start;
		}
		reverse_iterator rend()
		{
			return _finish;
		}
		const_reverse_iterator rbegin() const
		{
			return _start;
		}
		const_reverse_iterator rend() const
		{
			return _finish;
		}

		template<class... Args>
		void emplace_front(Args&&... args)
		{
			if ((_start - 1)._node == _map)
				reserve(_map_size * 2);
			if (_start._cur == _start._first)
			{
				if (_start._node[-1] == nullptr)
					_start._node[-1] = static_cast<T*>(operator new(sizeof(data_type) * BufSiz));
			}
			--_start;
			new(_start._cur)data_type(args...);
		}
		template<class... Args>
		void emplace_back(Args&&... args)
		{
			if ((_finish + 1)._node == _map + _map_size - 1)
				reserve(_map_size * 2);
			if (_finish._cur == _finish._last - 1)
			{
				if (_start._node[1] == nullptr)
					_start._node[1] = static_cast<T*>(operator new(sizeof(data_type) * BufSiz));
			}
			new(_finish._cur)data_type(args...);
			++_finish;
		}
		void push_front(const data_type& data)
		{
			emplace_front(data);
		}
		void push_front(data_type&& data)
		{
			emplace_front(qyc::forward<data_type>(data));
		}
		void pop_front() throw(std::out_of_range)
		{
			if (empty())
				throw std::out_of_range("err: deque:: empty()");
			(*_start).~data_type();
			++_start;
		}
		void push_back(const data_type& data)
		{
			emplace_back(data);
		}
		void push_back(data_type&& data)
		{
			emplace_back(qyc::forward<data_type>(data));
		}
		void pop_back() throw(std::out_of_range)
		{
			if (empty())
				throw std::out_of_range("err: deque:: empty()");
			--_finish;
			(*_finish).~data_type();
		}

		template <class... Args>
		iterator emplace(iterator pos, Args&&... args) throw(std::out_of_range)
		{
			if (pos < _start)
				throw std::out_of_range("err: deque:: pos < _start");
			if (pos > _finish)
				throw std::out_of_range("err: deque:: pos > _finish");
			if (_finish._node == _map + _map_size - 1)
			{
				size_t offset = pos - _start;
				reserve(_map_size * 2);
				pos = _start + offset;
			}
			size_t init_len = ((_finish._cur - _finish._first) + 1) / BufSiz;
			for (size_t i = 1; i <= init_len; ++i)
			{
				if (_finish._node[i] == nullptr)
					_finish._node[i] = static_cast<T*>(operator new(sizeof(data_type) * BufSiz));
			}
			iterator end = _finish;
			while (end > pos)
			{
				new(end._cur)data_type(qyc::move(end[-1]));
				end[-1].~data_type();
				--end;
			}
			new(end._cur)data_type(args...);
			++_finish;
			return pos;
		}
		iterator insert(iterator pos, const data_type& data) throw(std::out_of_range)
		{
			return emplace(pos, data);
		}
		iterator insert(iterator pos, data_type&& data) throw(std::out_of_range)
		{
			return emplace(pos, qyc::forward<data_type>(data));
		}
		iterator insert(iterator pos, size_t n, const data_type& data) throw(std::out_of_range)
		{
			if (pos < _start)
				throw std::out_of_range("err: deque:: pos < _start");
			if (pos > _finish)
				throw std::out_of_range("err: deque:: pos > _finish");
			if (n == 0)
				return pos;
			if ((_finish + n)._node == _map + _map_size - 1)
			{
				size_t offset = pos - _start;
				reserve((_map_size + ((n + (BufSiz - 1)) / BufSiz)) * 2);
				pos = _start + offset;
			}
			size_t init_len = ((_finish._cur - _finish._first) + n) / BufSiz;
			for (size_t i = 1; i <= init_len; ++i)
			{
				if (_finish._node[i] == nullptr)
					_finish._node[i] = static_cast<T*>(operator new(sizeof(data_type) * BufSiz));
			}
			iterator end = _finish - 1 + n;
			while (end > pos + n - 1)
			{
				new(end._cur)data_type(qyc::move(end[-n]));
				end[-1].~data_type();
				--end;
			}
			while (end >= pos)
			{
				new(end._cur)data_type(data);
				--end;
			}
			_finish += n;
			return pos;
		}
		iterator insert(iterator pos, int n, const data_type& x) throw(std::out_of_range)
		{
			return insert(pos, static_cast<size_t>(n), x);
		}
		iterator insert(iterator pos, long n, const data_type& x) throw(std::out_of_range)
		{
			return insert(pos, static_cast<size_t>(n), x);
		}
		template <class InputIterator>
		iterator insert(iterator pos, InputIterator first, InputIterator last) throw(std::out_of_range)
		{
			if (pos < _start)
				throw std::out_of_range("err: deque:: pos < _start");
			if (pos > _finish)
				throw std::out_of_range("err: deque:: pos > _finish");
			InputIterator tmp = first;
			size_t n = 0;
			while (tmp != last)
				++n, ++tmp;
			if ((_finish + n)._node == _map + _map_size - 1)
			{
				size_t offset = pos - _start;
				reserve((_map_size + ((n + (BufSiz - 1)) / BufSiz)) * 2);
				pos = _start + offset;
			}
			size_t init_len = ((_finish._cur - _finish._first) + n) / BufSiz;
			for (size_t i = 1; i <= init_len; ++i)
			{
				if (_finish._node[i] == nullptr)
					_finish._node[i] = static_cast<T*>(operator new(sizeof(data_type) * BufSiz));
			}
			iterator end = _finish - 1 + n;
			while (end > pos + n - 1)
			{
				new(end._cur)data_type(qyc::move(end[-n]));
				end[-n].~data_type();
				--end;
			}
			iterator ret = pos;
			while (pos <= end)
			{
				new(pos._cur)data_type(*first);
				++pos, ++first;
			}
			_finish += n;
			return ret;
		}

		iterator erase(iterator pos) throw(std::out_of_range)
		{
			if (pos < _start)
				throw std::out_of_range("err: deque:: pos < _start");
			if (pos >= _finish)
				throw std::out_of_range("err: deque::pos >= _finish");
			iterator begin = pos;
			while (begin + 1 < _finish)
			{
				new(begin._cur)data_type(qyc::move(begin[1]));
				begin[1].~data_type();
				++begin;
			}
			--_finish;
			(*_finish).~data_type();
			return pos;
		}
		iterator erase(iterator first, iterator last) throw(std::out_of_range)
		{
			if (first < _start)
				throw std::out_of_range("err: deque:: first < _start");
			if (first >= _finish)
				throw std::out_of_range("err: deque:: first >= _finish");
			if (last <= _start)
				throw std::out_of_range("err: deque:: first <= _start");
			if (last > _finish)
				throw std::out_of_range("err: deque:: last > _finish");
			size_t n = 0;
			iterator tmp = first;
			while (tmp != last)
				++n, ++tmp;
			while (first < last && (first + n) < _finish)
			{
				new(first._cur)data_type(qyc::move(first[n]));
				first[n].~data_type();
				++first;
			}
			for (size_t i = 1; i <= n; ++i, --_finish)
				(_finish[-1]).~data_type();
			return first;
		}

		reference operator[](long long n) throw(std::out_of_range)
		{
			if (_start + n >= _finish)
				throw std::out_of_range("err: deque:: empty()");
			return *(_start + n);
		}
		const_reference operator[](long long n) const throw(std::out_of_range)
		{
			if (_start + n >= _finish)
				throw std::out_of_range("err: deque:: empty()");
			return *(_start + n);
		}
		reference front() throw(std::out_of_range)
		{
			if (empty())
				throw std::out_of_range("err: deque:: empty()");
			return *_start;
		}
		reference back() throw(std::out_of_range)
		{
			if (empty())
				throw std::out_of_range("err: deque:: empty()");
			iterator tmp = _finish;
			--tmp;
			return *tmp;
		}
		const_reference front() const throw(std::out_of_range)
		{
			if (empty())
				throw std::out_of_range("err: deque:: empty()");
			return *_start;
		}
		const_reference back() const throw(std::out_of_range)
		{
			if (empty())
				throw std::out_of_range("err: deque:: empty()");
			const_iterator tmp = _finish;
			--tmp;
			return *tmp;
		}

		void reserve(size_t n)
		{
			if (_map_size >= n)
				return;
			map_pointer new_map = new data_type* [n] {nullptr};
			map_pointer new_begin = new_map + n / 2;
			
			map_pointer begin = _start._node;
			map_pointer first = _map;
			while (*first == nullptr)
				++first;
			new_begin = new_begin - (begin - first);
			_start._node = new_begin;

			for (size_t i = 0; begin[i] != nullptr && begin + i < _map + _map_size; ++i)
			{
				new_begin[i] = begin[i];
				begin[i] = nullptr;
				if (_finish._node == begin + i)
					_finish._node = new_begin + i;
			}
			delete[] _map;
			_map = new_map;
			_map_size = n;
		}
		void resize(size_t n, const data_type& data = data_type())
		{
			iterator i = begin();
			size_t len = 0;
			for (; i != end() && len < n; ++i, ++len);
			if (len <= n)
				insert(end(), n - len, data);
			else
				erase(i, end());
		}
		void clear()
		{
			map_pointer cur = _start._node;
			while (*cur != nullptr)
			{
				for (size_t i = 0; i < BufSiz; ++i)
					cur[0][i].~data_type();
				++cur;
			}
		}
		bool empty() const
		{
			return _finish == _start;
		}
		size_t size() const
		{
			return _finish - _start;
		}
		void swap(self& right)
		{
			qyc::swap(_start, right._start);
			qyc::swap(_finish, right._finish);
			qyc::swap(_map, right._map);
			qyc::swap(_map_size, right._map_size);
		}
		~deque()
		{
			for (size_t i = 0; i < _map_size; ++i)
			{
				if (_map[i] != nullptr)
				{
					if (_map + i == _start._node)
					{
						for (iterator begin = _start, prev = _start; begin < _finish; ++begin)
						{
							(*begin).~data_type();
							if (begin._node != prev._node)
							{
								operator delete(*prev._node);
								*prev._node = nullptr;
								++i;
								prev = begin;
							}
						}
					}
					operator delete(_map[i]);
					_map[i] = nullptr;
				}
			}
			delete[] _map;
		}
	private:
		size_t _map_size = 0;
		map_pointer _map = nullptr;
		iterator _start;
		iterator _finish;
	};
}